#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<int> loc(n + 1);
        Backtrack(1, loc, n, result);
        return result;
    }

    bool Place(const int i, const vector<int> loc) {
        for (int j = 1; j < i; j++) {
            if ((abs(i - j) == abs(loc[i] - loc[j])) || (loc[i] == loc[j])) {
                return false;
            }
        }
        return true;
    }

    void Backtrack(const int i, vector<int> loc, const int size, vector<vector<string>>& result) {
        if (i > size) {
            vector<string> solution;
            for (int j = 1; j <= size; j++) {
                string row(size, '.');
                row[loc[j] - 1] = 'Q';
                solution.push_back(row);
            }
            result.push_back(solution);
        }
        else {
            for (int j = 1; j <= size; j++) {
                loc[i] = j;
                if (Place(i, loc)) {
                    Backtrack(i + 1, loc, size, result);
                }
            }
        }
    }
};